/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：二进制链表转整数
 * 思路：
 *     1. 遍历链表将所有的节点值存储到顺序表中，再遍历顺序表将所有元素全部相加按照权重即可
 *     上述方法会超出内存限制
 *     2. 先反转原链表，再次从反转后的链表开始遍历，计算节点元素的值，按照权重相加即可
 */
public class Test {
    // 超出内存限制
    // public int getDecimalValue(ListNode head) {
    //     // 把链表中的节点全部遍历，其数据存储到数组中
    //     ListNode cur = head;
    //     ArrayList<Integer> list = new ArrayList<>(); // 创建一个顺序表用来存储数据
    //     int count = -1;
    //     while (cur != null) {
    //         count++;
    //         list.add(cur.val);
    //     }
    //     // 开始遍历顺序表相加元素值
    //     int sum = 0;
    //     for (int i = 0; i < list.size(); i++) {
    //         sum += list.get(i) * (int)Math.pow(2, count--);
    //     }
    //     return sum;
    // }

    public int getDecimalValue(ListNode head) {
        // 将链表反转
        ListNode cur = head.next;
        ListNode prev = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
            if (curNext != null) {
                curNext = curNext.next;
            }
        }
        // 开始遍历新链表，将遇到的值全部相加即可
        int sum = 0;
        int count = 0;
        while (prev != head) {
            sum += (prev.val) * (int)Math.pow(2, count++);
            prev = prev.next;
        }
        // 再将最后头节点的值相加即可
        sum += (prev.val) * (int)Math.pow(2, count++);
        return sum;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
